package com.algorithm.array;

public class FindMinLost {
    /**
     *@author : daniel.yang
     *@date : 2018/11/12
     *@desc : 给定一个未排序的整数数组，找出其中没有出现的最小的正整数。
     *@param args :
     *            思路:缺失的正整数必定小于数组长度(除非不缺失)
     */
    public static void main(String[] args) {
        int[] arr = {1,5,6,9,0,-4,2,6,4,3,8,99,14,11,20,};
        //第一步 如果v = arr[i]的值小于数组大小,将其放到arr[v-1]的位置,否则不动
        for (int i = 0; i < arr.length; i++) {
            int v = arr[i];
            if (v > 0 && v < arr.length){
                //交换arr[i]和arr[v-1]
                int temp = arr[i];
                arr[i] = arr[v -1];
                arr[v-1] = temp;
            }
        }
        // 第二步 从1开始递增扫描数组,arr[i] != i+1 的既是答案
        int res = -1;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] != i+1){
                res = i+1;
                break;
            }
        }
        System.out.println(res);
    }
}
